package anthology.daily_question._25_02;
//https://leetcode.cn/problems/replace-elements-with-greatest-element-on-right-side/description/?envType=daily-question&envId=2025-02-16
public class _1299将每个元素替换为右侧最大元素 {
    class Solution {
        public int[] replaceElements(int[] arr) {
            int length = arr.length;
            int[] tmp = new int[length];
            for(int i = 0; i<length-1; i++){
                int max = -1;
                for(int j = i+1; j<length; j++){
                    if(arr[j] > max){
                        max = arr[j];
                    }
                }
                tmp[i] = max;
            }
            tmp[length-1] = -1;
            return tmp;
        }
    }
    class Solution2 {
        public int[] replaceElements(int[] arr) {
            int n = arr.length;
            int[] ans = new int[n];
            ans[n - 1] = -1;
            for (int i = n - 2; i >= 0; --i) {
                ans[i] = Math.max(ans[i + 1], arr[i + 1]);
            }
            return ans;
        }
    }
    class Solution3 {
        public int[] replaceElements(int[] arr) {
            int mx = -1;
            for (int i = arr.length - 1; i >= 0; i--) {
                int x = arr[i];
                arr[i] = mx;
                mx = Math.max(mx, x); // 维护后缀最大值
            }
            return arr;
        }
    }
}
